package org.example.algorithm.find;

import java.util.PriorityQueue;

public class FindKthLargestSolution {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 8, 7};
        int order = 2;
        FindKthLargestSolution solution = new FindKthLargestSolution();
        int res = solution.findKthLargest(arr, order);
        System.out.println(res);
    }

    /**
     * 使用优先级队列作为最小堆
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i=0; i<nums.length;i++) {
            priorityQueue.offer(nums[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }

    /**
     * 快排方式查找
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest2(int[] nums, int k) {
        int pos = partition(nums, 0, nums.length-1, nums.length - k);
        if (pos >= 0) {
            return nums[pos];
        } else {
            return -1;
        }
    }

    public int partition(int[] nums, int start, int end, int order) {
        if (start == end) {
            if (start == order) {
                return start;
            } else {
                return -1;
            }
        }
        int compare = nums[end];
        int j=start-1;
        for (int i=start;i<=end;i++) {
            if (nums[i] < compare) {
                swap(nums, i, ++j);
            }
        }
        swap(nums, end, ++j);
        if (j == order) {
            return j;
        }
        if (j > order) {
            return partition(nums, start, j-1, order);
        } else {
            return partition(nums, j+1, end, order);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
